<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <!-- 基于 js 的语法, 设计一个函数, 实现一个冒泡排序和一个快速排序. 在控制台输出排序结果. 
     前一个与后一个元素相比，如果比它大，便往后移动 -->
    <script>
        // 冒泡排序
        let arr1 = [10, 8, 2, 9, 20, 1];
        for(let i = 0; i < arr1.length-1; i++) {
            for(let j = 0; j < arr1.length-1-i; j++) {
                if(arr1[j] > arr1[j+1]) {
                    let temp = arr1[j];
                    arr1[j] = arr1[j+1];
                    arr1[j+1] = temp;
                }
            }
        }
        console.log(arr1);

        // 快速排序
        let arr = [20, 7, 3, 90, 25, 5];
        // 找出中间值，分离函数：左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值
        function partition(arr, left, right) {
            let i = left;
            let j = right;
            let pivot = left;
            while (i < j) {
                while (i < j && arr[j] > arr[pivot]) {
                    j--;
                }
                while(i < j && arr[i] < arr[pivot]) {
                    i++;
                }
                swap(arr, i, j);
            } 
            swap(arr, i, pivot); // 设置新的基准值
            return i; // 新的基准值
        }
        // 自身递归 实现快排
        function quickSort(arr, left, right) {
            if(left > right) {
                return;
            }
            let mid = partition(arr, left, right);
            quickSort(arr, left, mid-1);
            quickSort(arr, mid+1, right);
        }
        function swap(arr, i, j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        quickSort(arr, 0, arr.length-1);
        console.log(arr);
    </script>


     <!-- 设计一个函数实现二分查找（折半查找）的逻辑 -->
    <script>
        let arr2 = [5, 13, 24, 35, 40, 56, 90];
        function binarySearch (arr2, key) {
            let left = 0;
            let right = arr2.length - 1;
            while(left < right) {     
                let mid = (left + right) / 2;
                if(key == arr2[mid]) {
                    return mid;
                }else if(key < arr2[mid]) {
                    right = mid - 1;
                }else if(key > arr2[mid]) {
                    left = mid + 1;
                } else {
                    return -1;
                }
            }
        }
        let mid = binarySearch(arr2, 35);
        console.log(mid);
    </script>
</body>
</html>